package com.googlecode.gaal.analysis.impl;

import com.googlecode.gaal.analysis.api.IntervalSetBuilder;
import com.googlecode.gaal.data.api.IntSequence;
import com.googlecode.gaal.data.api.IntervalSet;
import com.googlecode.gaal.data.impl.IntervalBitSet;
import com.googlecode.gaal.suffix.api.BinaryIntervalTree;
import com.googlecode.gaal.suffix.api.BinaryIntervalTree.BinaryNode;
import com.googlecode.gaal.suffix.api.SuffixArray;

public class SingletonBwtSetBuilder implements IntervalSetBuilder {

    @Override
    public <E extends BinaryNode<E>, T extends SuffixArray & BinaryIntervalTree<E>> IntervalSet<E> buildIntervalSet(
            T tree) {
        IntervalSet<E> bwtSet = new IntervalBitSet<E>(tree);
        traverse(bwtSet, tree, tree.top());
        return bwtSet;

    }

    private <E extends BinaryNode<E>> int traverse(IntervalSet<E> bwtSet, SuffixArray sa, E interval) {
        if (interval.isTerminal()) {
            int loc = sa.getSuffixTable()[interval.left()];
            IntSequence sequence = sa.getSequence();
            if (loc == 0)
                return sequence.get(sequence.size() - 1);
            else
                return sequence.get(loc - 1);
        } else {
            E left = interval.leftChild();
            E right = interval.rightChild();

            int leftValue = traverse(bwtSet, sa, left);
            int rightValue = traverse(bwtSet, sa, right);
            if (leftValue == -1 || leftValue != rightValue) {
                return -1;
            } else {
                bwtSet.add(interval);
                return leftValue;
            }
        }
    }
}
